//
// Created by 123 on 2024/4/1.
//
/**
 * 堆排序
 *      首先建立大根堆
 *
 *
 *     更新 n 轮最小位置
 *     即成
 *
 *      O(nlog n)
 */
#include <iostream>

using namespace std;

#define MaxSize 100

typedef struct Array {
    int data[MaxSize];
    int length;
} Array, *Arr;

Array *initArray(int arr[], int len);

void swap(int &a, int &b);

void buildMaxHeap(Arr &arr, int len);

void heapAdjust(Arr &arr, int num_index, int len);
void heapify(Arr &arr,int num_index,int len);
void heapInsert(Arr &arr,int num);
void heapDelete(Arr &arr);

void heap_sort(Arr &arr);


int main() {
    int a[10]{49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
    Arr arr = initArray(a, 10);
    buildMaxHeap(arr,arr->length);

    heapInsert(arr,99);
    for (int i = 0; i < arr->length; ++i) {
        cout << arr->data[i] << "    ";
    }
    cout<<endl;
    heapDelete(arr);
    heapDelete(arr);
    for (int i = 0; i < arr->length; ++i) {
        cout << arr->data[i] << "    ";
    }
    cout<<endl;

    heap_sort(arr);

    for (int i = 0; i < arr->length; ++i) {
        cout << arr->data[i] << "    ";
    }
}

void heap_sort(Arr &arr) {
    buildMaxHeap(arr,arr->length);
    for (int i = arr->length; i >0; --i) {
        swap(arr->data[i-1],arr->data[0]);
        heapAdjust(arr,0,i-1);
//        heapify(arr,0,i-1);
    }
}

void buildMaxHeap(Arr &arr, int len) {
    for (int i = (len-2)/2; i >=0; --i) {
        heapAdjust(arr,i,len);
//        heapify(arr,i,len);
    }
}

void heapAdjust(Arr &arr, int num_index, int len) {
    int num = arr->data[num_index];
    for (int i = num_index*2+1; i < len; i =i  * 2+1) {
        if(i+1<len&&arr->data[i]<arr->data[i+1])
            i++;
        if(num>arr->data[i])
            break;
        else{
            arr->data[num_index]=arr->data[i];
            num_index=i;
        }
    }
    arr->data[num_index]=num;
}
void heapify(Arr &arr,int num_index,int len){
    int left=num_index*2+1;
    while (left<len){
        int largest=left+1<len&&arr->data[left+1]>arr->data[left]?left+1:left;
        largest=arr->data[largest]>arr->data[num_index]?largest:num_index;
        if(largest==num_index)
            break;
        swap(arr->data[largest],arr->data[num_index]);
        num_index=largest;
        left=num_index*2+1;
    }
}
void heapInsert(Arr &arr,int num){
    arr->data[arr->length++]=num;
    int len=arr->length-1;
    while (arr->data[(len-1)/2]<arr->data[len]){
        swap(arr->data[(len-1)/2],arr->data[len]);
        len=(len-1)/2;
    }
}
void heapDelete(Arr &arr){
    swap(arr->data[0],arr->data[arr->length-1]);
    arr->length=arr->length-1;
    heapify(arr,0,arr->length);
}

Array *initArray(int arr[], int len) {
    Arr array = (Array *) malloc(sizeof(Array));
    for (int i = 0; i < len; ++i) {
        array->data[i] = arr[i];
    }
    array->length = len;
    return array;
}

void swap(int &a, int &b) {
    int turn = a;
    a = b;
    b = turn;
}